package com.wn.date20190814linkedList;

import java.util.Iterator;

/**
 * 双向循环链表
 * @author song
 *
 */
public class LinkedList implements Iterable<Object>
{
	private Node first;
	private Node last;
	private int size=0;
	
	/**
	 * 节点
	 * @author song
	 *
	 */
	private class Node
	{
		Node next;
		Object element;
		Node prev;

		public Node(Node prev,Object obj,Node next)
		{
			this.prev=prev;
			this.element=obj;
			this.next=next;
		}

		
	}
	/**
	 * 移除索引位置节点
	 * @param index
	 * @return
	 */
	public Object remove(int index)
	{
		if(index<0||index>=size)
		{
			return false;
		}
		Node delete=getNode(index);
		final Object elment=delete.element;
		// 删除首节点
		if(index==0)
		{
			first=delete.next;
			// 只有一个节点
			if(size==1)
			{
				first.prev=null;
				first.next=null;
				first=null;
			}
		}
		if(index==size-1)
		{
			last=delete.prev;
			// 只有一个节点
			if(size==1)
			{
				last.prev=null;
				last.next=null;
				last=null;
			}
		}
		// unlink
		delete.prev.next=delete.next;
		delete.next.prev=delete.prev;
		// 清空节点
		delete.prev=null;
		delete.next=null;
		delete.element=null;
		delete=null;
		size--;
		
		return elment;
	}
	/**
	 * 获取根据索引取节点的elment,越界则返回first
	 * @param index
	 * @return
	 */
	public Object get(int index)
	{
		return getNode(index).element;
	}
	public Object getFirst()
	{
		return first.element;
	}
	public Object getLast()
	{
		return last.element;
	}
	/**
	 * 添加
	 * @param obj
	 * @return
	 */
	public boolean add(Object obj)
	{
		// 第一个元素
		if(size==0)
		{
			Node newNode=new Node(null, obj, null);
			newNode.prev=newNode;
			newNode.next=newNode;
			size++;
			first=newNode;
			last=newNode;
		}
		else // 后续元素
		{
			Node newNode=new Node(last, obj, first);
			size++;
			last.next=newNode;
			newNode.prev=last;
			last=newNode;
		}
		return true;
	}
	/**
	 * 插在索引位置
	 * @param index
	 * @param obj
	 * @return
	 */
	public boolean add(int index, Object obj)
	{
		if(index<0||index>size)
		{
			return false;
		}
		// 尾部加
		if(index==size)
		{
			add(obj);
		}else {
			Node oldNode=getNode(index);
			Node newnoNode=new Node(null, obj, null);
			// 插入
			oldNode.prev.next=newnoNode;  // 前。next—>new
			newnoNode.prev=oldNode.prev; // new.pre->前
			newnoNode.next=oldNode;// new.next->旧
			oldNode.prev=newnoNode; // 旧.prev->新
			size++;
		}
		return true;
	}
	
	/**
	 * 根据索引取节点,越界则返回first
	 * @param index
	 * @return
	 */
	public Node getNode(int index)
	{
		if(index<0||index>=size)
		{
			return first;
		}
		// 前半段
		if(index<(size>>1))
		{
			// 找到当前index位置节点
			Node x=first;
			for(int i=0;i<index;i++)
			{
				x=x.next;
			}
			return x;
		}else // 后半段
		{
			Node x=last;
			for(int i=0;i<size-index-1;i++)
			{
				x=x.prev;
			}
			return x;
		}
	}
	
	@Override
	public Iterator<Object> iterator()
	{
		return new Iterator<Object>()
		{
			int count=0;
			@Override
			public boolean hasNext()
			{
				return size>count;
			}

			@Override
			public Object next()
			{
				return get(count++);
			}
			@Override
			public void remove()
			{
				///////// 调方法？？？？？？？？/////////////////////////////////
				first.next.prev=last;
				last.next=first.next;
				first=first.next;
			}
		};
	}
	/**
	 * 获取大小
	 * @return
	 */
	public int size()
	{
		return size;
	}
	
}
